class Solution {
    public boolean isMatch(String s, String p) {
        //动态规划
        int len1 = s.length();
        int len2 = p.length();
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        boolean[][] dp = new boolean[len1+1][len2+1];
        dp[0][0] = true;
        for(int i = 1; i<=len2 ; i++){
            if(p1[i-1] == '*'){
                dp[0][i] = true;
            }else{
                break;
            }
        }
        for(int i = 1 ; i <= len1 ; i++){
            for(int j = 1 ; j <= len2 ; j++){
                //表示说可以匹配
                if(s1[i-1] == p1[j-1] || p1[j-1]=='?'){
                    dp[i][j] = dp[i-1][j-1];
                //如果匹配符为*，有两种情况，一种是匹配空，一种是匹配字符串
                }else if(p1[j-1] == '*'){
                    //
                    dp[i][j] =  dp[i][j-1] || dp[i-1][j] ;
                }
            }
        }
        return dp[len1][len2];
    }
}